class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode* lessGuard=(ListNode*)malloc(sizeof(ListNode));
        ListNode* greaterGuard=(ListNode*)malloc(sizeof(ListNode));
        ListNode*cur=pHead;
        ListNode* lessTail=lessGuard;
        ListNode* greaterTail=greaterGuard;
        while(cur)
        {
            if(cur->val<x)
            {
                lessTail->next=cur;
                lessTail=lessTail->next;                
            }
            else
            {
                greaterTail->next=cur;
                greaterTail=greaterTail->next;
               
            }
            cur=cur->next;
        }
        lessTail->next=greaterGuard->next;
        greaterTail->next=NULL;
       pHead=lessGuard->next;
        free(lessGuard);
        free(greaterGuard);
        return pHead;        
    }
};
